// 基数排序
/*
对 a[n]进行基数排序
1.确定关键字基数Ra 例如  十进制 基数为 10 二进制 基数为2
2.开辟基数表头r_box[n][Ra] 十进制就开辟一个长度为10的指针数组 二进制就开辟一个长为2的指针数组
r_box[n+1][Ra] :r_box[0][Ra]表示当前序列中元素个数
3.找到最大位数 max_r
4.for(i=0->max_r) 从第0位开始
5.for(j=0->n) 遍历待排序列a[n]
6.index=get(a[j],i) 获取a[j]第i位数
7.k=++r_box[0][index] 索引+1
8.r_box[k][index]=a[j] a[j]加到这一列中
9.把表头的元素复制到a[]中
    1.for(int m=0;m<Ra;m++) 遍历表头
        for(int n=0;n<r_box[0][m];n++) 遍历某一位的所有元素
            a[t++]=r_box[n][m];
        r_box[0][m]=0;!!!!归零 进行下一位的排序
回到5
回到4
*/
#include <stdio.h>
#include <stdlib.h>
#define RA 10 //十进制基数排序
int getmax(int a[], int n)
{
    int max = -66666;
    for (int i = 0; i < n; i++)
        if (max < a[i])
            max = a[i];
    int k = 0;
    while (max > 0)
    {
        max /= 10;
        k++;
    }
    return k;
}
//返回a 的第j位 不足j位 返回0
int get_r(int a, int j)
{
    while (j > 1)
    {
        j--;
        a /= 10;
    }
    return (a % 10);
}
void radix_sort(int a[], int n)
{
    //开辟 r_box 只能动态分配内存
    int *r_box[RA];
    for (int r = 0; r < n; r++)
    {
        r_box[r] = (int *)malloc(sizeof(int) * (n + 1));
        r_box[r][0] = 0;
    }
    //取序列内最大数的位数
    int m_r = getmax(a, n);
    //对于第i位进行排序
    for (int i = 0; i < m_r; i++)
    {

        for (int j = 0; j < n; j++)
        {
            int index = get_r(a[j], i + 1);
            r_box[index][++r_box[index][0]] = a[j];
        }
        int t = 0;
        //把表内数据赋值给a[]
        for (int m = 0; m < RA; m++)
        {
            for (int n = 1; n <= r_box[m][0]; n++)
            {
                a[t++] = r_box[m][n];
            }
            r_box[m][0] = 0; //!!!! 一定要归零
        }
        //此时a[]内是按照第(i+1)位排序好了的序列
    }
}

void main()
{
    int a[] = {4, 3, 8, 2, 7, 11, 6, 1, 0, 15};
    radix_sort(a, 10);
    for (int i = 0; i < 10; i++)
        printf("%3d", a[i]);
}
